package SwordFingerOffer;

public class Q33_VerifyTreePostorder {
    //验证一个序列是否为某二叉搜索树的后续序列
    //本题与 二叉树 前中序推后续解法与破题点上有着微妙的联系
    //简单说 一个点 左边的都比根小 右边的都比根大 去递归就完事

    public boolean verifyPostorder(int[] postorder) {
        if (postorder == null) {
            return false;
        }
        return process(postorder, 0, postorder.length - 1);
    }


    public boolean process(int[] postorder,int left, int right) {
        if (left >= right){
            return true;
        }
        //可以确定根节点
        int root = postorder[right];

        //左边按照[左][右]我 根据二叉搜索树特性 左都比我小 右都比我大
        //下面要找到右区间去递归 既找到第一个比我大的
        //注意这一步就算是验证了待会算出来的左区间是否都比root小 既边算边验证
        int i = left;
        while (i < right && postorder[i] <= root){
            i++;
        }
        //无右子树 左边递归去
        if (i == right){
            return process(postorder, left, i - 1);
        }else{
            //右子树有区间 正常判定
            for (int j = i; j < right; j++) {
                if (postorder[j] < root){
                    return false;
                }
            }
        }

        return process(postorder, left, i - 1) && process(postorder, i, right - 1);
    }


    public static void main(String[] args) {
        Q33_VerifyTreePostorder fun = new Q33_VerifyTreePostorder();
        System.out.println(fun.verifyPostorder(new int[]{1,2,5,10,6,9,4,3}));
    }
}
